/* SexpFormatter.cs -- s-expression serialization formatter.
   Copyright (C) 2008  Casey Marshall.

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or (at
your option) any later version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.  */


using System;
using System.Diagnostics;
using System.Collections.Generic;
using System.IO;
using System.Reflection;
using System.Reflection.Emit;
using System.Runtime.Remoting;
using System.Runtime.Remoting.Messaging;
using System.Runtime.Serialization;
using System.Text;

using SexpSharp;
using SexpSharp.Remoting;

namespace SexpSharp.Serialization
{
    /// <summary>
    /// A serialization formatter for s-expressions.
	///
	/// The serialization format of an object is this:
	///
	///   (type [assembly] value)
    ///
	/// `type' is a UTF-8 string denoting the C# type of the object;
	/// `assembly' is an optional UTF-8 string denoting the assembly
	/// the object can be found in. `value' is an expression containing
	/// the object value.
    ///
	/// Null references are special, in that there is no type or value.
	/// They are represented by the empty list.
	///
    /// For certain primitive types, the value is an atom, and the type
	/// field is a special value, one of:
	///
	///   .u1       A Byte. Stored as a byte.
	///   .s1       A SByte. Stored as a byte.
	///   .s2       An Int16. Stored as two big-endian bytes.
	///   .u2       An UInt16.
	///   .s4       An Int32. Stored as four big-endian bytes.
	///   .u4       An UInt32.
	///   .s8       An Int64. Stored as eight big-endian bytes.
	///   .u8       An UInt64.
	///   .b        A Boolean. Stored as the strings "true" or "false".
	///   .D        A Decimal. Stored as the value in scientific
	///             notation [+-]XXXe[+-]XX.
	///   .d        A Double. Stored in scientific notation.
	///   .f        A Single. Stored in scientific notation.
	///   .s        A string. Stored as the UTF-8 bytes of the string.
	///   .r        A reference to another object (to resolve cycles).
	///
	/// There are also the internal types:
	///
	///   .arrayof  An array of primitive values.
	///   .array    A plain array.
	///
	/// Arrays are handled specially. Primitive integral arrays are
	/// stored as:
	///
	///   (.arrayof TYPE VALUE)
	///
	/// Where TYPE might be .byte, .short, .int, etc. VALUE is stored
	/// as the raw values as a byte string. That is, a byte array with
	/// 42 entries will have a byte string of 42 bytes; an integer
	/// array with 10 entries will have a byte string of 40 bytes.
	/// Each multibyte element is stored in big-endian order
	///
	/// Regular arrays have a value that is simply a list of
	/// subexpressions. That is:
	///
	///   (.array (VALUES...))
	///
	/// E.g., an array of strings:
	///
	///   (.array ((.s "foo") (.s "bar") (.s "baz")))
	///
	/// When deserializing, if an array has a common type, the
	/// returned object will be an array of that type. That is, the
	/// array of strings above would be deserialized into a string[].
	///
	/// Enums are handled as the triplet:
	///
	///   (.e typename value)
	///
	/// `typename' is the enum's type name, and `value' is a integer
	/// value (in a packed representation; if the value can be expressed
	/// in two bytes, value is two bytes long).
	///
	/// Classes are encoded as a list of key-value pairs. That is, an
	/// object value is encoded as a list of:
	///
    ///   (fieldname value)
	///
	/// expressions. So a simple class Foo might encode to:
	///
	///   (Foo ((stringVal (.s "string value"))
    ///         (intVal (.s4 |YWJjZA==|))))
    ///
    /// </summary>
    public sealed class SexpFormatter : IRemotingFormatter, IFormatter
    {
		private SerializationBinder binder;
		private StreamingContext context;
		private ISurrogateSelector selector;
		private Dictionary<BooleanParameter, bool> boolParams;
		private Format format;

		private TypeCache cache;

		public enum BooleanParameter
		{
			IgnoreExtraFields
		}

		public SexpFormatter() : this(new TypeCache())
        {
        }

        public SexpFormatter(TypeCache cache)
		{
			InitTypeMap();
			binder = null;
			selector = null;
			boolParams = new Dictionary<BooleanParameter, bool>();
			boolParams[BooleanParameter.IgnoreExtraFields] = false;
			format = Format.Verbatim;
			context = new StreamingContext(StreamingContextStates.All);
			this.cache = cache;
		}

        const string RPCHeader = "srpc";
        const int RPCVersion = 1;
		const string SerialHeader = "serial-object";
		const int SerialVersion = 1;

		public object Deserialize(Stream input)
		{
			Expression e = Parser.Parse(input);
			if (e == null)
				throw new IOException("end of input while deserializing");
			if (!(e is List))
				throw new SerializationException("expecting a list");
			List serial = e as List;
			if (serial.Count != 3)
				throw new SerializationException("expecting exactly three expressions");
			Atom header = serial[0] as Atom;
			Atom version = serial[1] as Atom;
			List obj = serial[2] as List;
			if (header == null || header.ToString() != SerialHeader)
				throw new SerializationException("invalid header");
			if (version == null || version.ToInteger() != SerialVersion)
				throw new SerializationException("invalid version");
			if (obj == null)
				throw new SerializationException("invalid object");
			
			return ListToObject(obj);
		}

		public object Deserialize(Stream input, HeaderHandler handler)
		{
			Expression e = Parser.Parse(input);
			if (e == null)
				throw new IOException("end of input while deserializing");
			if (!(e is List))
				throw new SerializationException("expecting a list");
			List srpc = e as List;
			if (srpc.Count != 4)
				throw new SerializationException("expecting four expressions");
			Atom header = srpc[0] as Atom;
			Atom version = srpc[1] as Atom;
			List headerList = srpc[2] as List;
			List obj = srpc[3] as List;
			if (header == null || header.ToString() != RPCHeader)
				throw new SerializationException("invalid header");
			if (version == null || version.ToInteger() != RPCVersion)
				throw new SerializationException("invalid version");
			if (headerList == null)
				throw new SerializationException("invalid headers");
			if (obj == null)
				throw new SerializationException("invalid object");

			Header[] headers = new Header[headerList.Count];
			int i = 0;
			foreach (Expression ee in headerList)
			{
				List h = ee as List;
				if (h == null)
					throw new SerializationException("invalid RPC header");
				if (h.Count != 2)
					throw new SerializationException("invalid RPC header");
				Atom name = h[0] as Atom;
				List value = h[1] as List;
				if (name == null)
					throw new SerializationException("invalid RPC header name");
				if (value == null)
					throw new SerializationException("invalid RPC header value");
				headers[i++] = new Header(name.ToString(), ListToObject(value));
			}
			if (handler != null)
				handler(headers);

			return ListToObject(obj);
		}

		public void Serialize(Stream output, object o)
		{
			List serial = new List();
			serial.Add(new Atom(SerialHeader));
			serial.Add(new Atom((uint) SerialVersion, true));
			serial.Add(ObjectToList(o));
            serial.Write(output, format);
		}

		public void Serialize(Stream output, object o, Header[] headers)
		{
			List srpc = new List();
			srpc.Add(new Atom(RPCHeader));
			srpc.Add(new Atom(RPCVersion, true));
			List headerList = new List();
			if (headers != null)
			{
				foreach (Header h in headers)
				{
					List header = new List();
					header.Add(new Atom(h.Name));
					header.Add(ObjectToList(h.Value));
					headerList.Add(header);
				}
			}
			srpc.Add(headerList);
			srpc.Add(ObjectToList(o));
			srpc.Write(output, format);
		}

		public SerializationBinder Binder
		{
			get {
				return binder;
			}

			set {
				this.binder = value;
			}
		}

		public StreamingContext Context
		{
			get {
				return context;
			}

			set {
				context = value;
			}
		}

		public ISurrogateSelector SurrogateSelector
		{
			get {
				return selector;
			}

			set {
				selector = value;
			}
		}

		public bool this[BooleanParameter param]
		{
			get {
				return boolParams[param];
			}

			set {
				boolParams[param] = value;
			}
		}

		public Format SerializeFormat
		{
			get {
				return format;
			}

			set {
				format = value;
			}
		}

        private class __proxy_bag
        {
            public object value;
        }

        private abstract class __func_bag_base
        {
            protected object target;
            protected DynamicMethod dm;
            protected __func_bag_base(object target, DynamicMethod dm)
            {
                this.target = target;
                this.dm = dm;
            }
        }

        private class __func_bag<TReturn> : __func_bag_base
        {
            public __func_bag(object target, DynamicMethod dm) : base(target, dm) { }
            public TReturn do_invoke()
            {
                return (TReturn) dm.Invoke(target, new object[] { target });
            }
        }

        private class __func_bag<T, TReturn> : __func_bag_base
        {
            public __func_bag(object target, DynamicMethod dm) : base(target, dm) { }
            public TReturn do_invoke(T arg)
            {
                return (TReturn) dm.Invoke(target, new object[] { target, arg });
            }
        }

        private class __func_bag<T1, T2, TReturn> : __func_bag_base
        {
            public __func_bag(object target, DynamicMethod dm) : base(target, dm) { }
            public TReturn do_invoke(T1 arg1, T2 arg2)
            {
                return (TReturn) dm.Invoke(target, new object[] { target, arg1, arg2 });
            }
        }

        private class __func_bag<T1, T2, T3, TReturn> : __func_bag_base
        {
            public __func_bag(object target, DynamicMethod dm) : base(target, dm) { }
            public TReturn do_invoke(T1 arg1, T2 arg2, T3 arg3)
            {
                return (TReturn) dm.Invoke(target, new object[] { target, arg1, arg2, arg3 });
            }
        }

        private class __func_bag<T1, T2, T3, T4, TReturn> : __func_bag_base
        {
            public __func_bag(object target, DynamicMethod dm) : base(target, dm) { }
            public TReturn do_invoke(T1 arg1, T2 arg2, T3 arg3, T4 arg4)
            {
                return (TReturn) dm.Invoke(target, new object[] { target, arg1, arg2, arg3, arg4 });
            }
        }

        private delegate TReturn __func<T1, T2, T3, T4, T5, TReturn>(T1 a1, T2 a2, T3 a3, T4 a4, T5 a5);

        private static Type __proxy_bag_type = typeof(__proxy_bag);
        private static FieldInfo __proxy_value_info;

		internal delegate object ConvertAtom(Atom a);
		internal delegate Atom ConvertPrim(object o);
		private static object typeMapLock = new object();
		internal static Dictionary<string, ConvertAtom> decMap;
        internal static Dictionary<string, Type> decTypes;
		internal static Dictionary<Type, ConvertPrim> encMap;
		internal static Dictionary<Type, string> encNames;

		internal static void InitTypeMap()
		{
			lock (typeMapLock)
			{
                if (__proxy_value_info == null)
                    __proxy_value_info = __proxy_bag_type.GetField("value");

				if (decMap == null)
				{
					decMap = new Dictionary<string, ConvertAtom>();
					decMap[BoolType]    = new ConvertAtom((a) => Convert.ToBoolean(a));
					decMap[ByteType]    = new ConvertAtom((a) => Convert.ToByte(a));
					decMap[SByteType]   = new ConvertAtom((a) => Convert.ToSByte(a));
					decMap[CharType]    = new ConvertAtom((a) => Convert.ToChar(a));
					decMap[ShortType]   = new ConvertAtom((a) => Convert.ToInt16(a));
					decMap[UShortType]  = new ConvertAtom((a) => Convert.ToUInt16(a));
					decMap[IntType]     = new ConvertAtom((a) => Convert.ToInt32(a));
					decMap[UIntType]    = new ConvertAtom((a) => Convert.ToUInt32(a));
					decMap[LongType]    = new ConvertAtom((a) => Convert.ToInt64(a));
					decMap[ULongType]   = new ConvertAtom((a) => Convert.ToUInt64(a));
					decMap[DecimalType] = new ConvertAtom((a) => Convert.ToDecimal(a));
					decMap[DoubleType]  = new ConvertAtom((a) => Convert.ToDouble(a));
					decMap[FloatType]   = new ConvertAtom((a) => Convert.ToSingle(a));
					decMap[StringType]  = new ConvertAtom((a) => Convert.ToString(a));
				}

                if (decTypes == null)
                {
                    decTypes = new Dictionary<string, Type>();
                    decTypes[BoolType]    = typeof(Boolean);
					decTypes[ByteType]    = typeof(Byte);
					decTypes[SByteType]   = typeof(SByte);
					decTypes[CharType]    = typeof(Char);
					decTypes[ShortType]   = typeof(Int16);
					decTypes[UShortType]  = typeof(UInt16);
					decTypes[IntType]     = typeof(Int32);
					decTypes[UIntType]    = typeof(UInt32);
					decTypes[LongType]    = typeof(Int64);
					decTypes[ULongType]   = typeof(UInt64);
					decTypes[DecimalType] = typeof(Decimal);
					decTypes[DoubleType]  = typeof(Double);
					decTypes[FloatType]   = typeof(Single);
					decTypes[StringType]  = typeof(String);
                }

				if (encMap == null)
				{
					encMap = new Dictionary<Type, ConvertPrim>();
					encMap[typeof(Boolean)] = new ConvertPrim((o) => new Atom((bool) o));
					encMap[typeof(Byte)]    = new ConvertPrim((o) => new Atom((byte) o));
					encMap[typeof(SByte)]   = new ConvertPrim((o) => new Atom((byte) o));
					encMap[typeof(Char)]    = new ConvertPrim((o) => new Atom((char) o));
					encMap[typeof(Int16)]   = new ConvertPrim((o) => new Atom((short) o));
					encMap[typeof(Int32)]   = new ConvertPrim((o) => new Atom((int) o));
					encMap[typeof(Int64)]   = new ConvertPrim((o) => new Atom((long) o));
					encMap[typeof(UInt16)]  = new ConvertPrim((o) => new Atom((ushort) o));
					encMap[typeof(UInt32)]  = new ConvertPrim((o) => new Atom((uint) o));
					encMap[typeof(UInt64)]  = new ConvertPrim((o) => new Atom((ulong) o));
					encMap[typeof(Decimal)] = new ConvertPrim((o) => new Atom((decimal) o));
					encMap[typeof(Single)]  = new ConvertPrim((o) => new Atom((float) o));
					encMap[typeof(Double)]  = new ConvertPrim((o) => new Atom((double) o));
					encMap[typeof(String)]  = new ConvertPrim((o) => new Atom((string) o));
					encMap[typeof(Nullable<Boolean>)] = new ConvertPrim((o) => new Atom((bool) o));
					encMap[typeof(Nullable<Byte>)]    = new ConvertPrim((o) => new Atom((byte) o));
					encMap[typeof(Nullable<SByte>)]   = new ConvertPrim((o) => new Atom((byte) o));
					encMap[typeof(Nullable<Char>)]    = new ConvertPrim((o) => new Atom((char) o));
					encMap[typeof(Nullable<Int16>)]   = new ConvertPrim((o) => new Atom((ushort) o));
					encMap[typeof(Nullable<Int32>)]   = new ConvertPrim((o) => new Atom((uint) o));
					encMap[typeof(Nullable<Int64>)]   = new ConvertPrim((o) => new Atom((ulong) o));
					encMap[typeof(Nullable<UInt16>)]  = new ConvertPrim((o) => new Atom((ushort) o));
					encMap[typeof(Nullable<UInt32>)]  = new ConvertPrim((o) => new Atom((uint) o));
					encMap[typeof(Nullable<UInt64>)]  = new ConvertPrim((o) => new Atom((ulong) o));
					encMap[typeof(Nullable<Decimal>)] = new ConvertPrim((o) => new Atom((decimal) o));
					encMap[typeof(Nullable<Single>)]  = new ConvertPrim((o) => new Atom((float) o));
                    encMap[typeof(Nullable<Double>)]  = new ConvertPrim((o) => new Atom((double) o));
				}

				if (encNames == null)
				{
					encNames = new Dictionary<Type, string>();
					encNames[typeof(Boolean)]           = BoolType;
					encNames[typeof(Byte)]              = ByteType;
					encNames[typeof(SByte)]             = SByteType;
					encNames[typeof(Char)]              = CharType;
					encNames[typeof(Int16)]             = ShortType;
					encNames[typeof(Int32)]             = IntType;
					encNames[typeof(Int64)]             = LongType;
					encNames[typeof(UInt16)]            = UShortType;
					encNames[typeof(UInt32)]            = UIntType;
					encNames[typeof(UInt64)]            = ULongType;
					encNames[typeof(Decimal)]           = DecimalType;
					encNames[typeof(Single)]            = FloatType;
					encNames[typeof(Double)]            = DoubleType;
					encNames[typeof(String)]            = StringType;
					encNames[typeof(Nullable<Boolean>)] = BoolType;
					encNames[typeof(Nullable<Byte>)]    = ByteType;
					encNames[typeof(Nullable<SByte>)]   = SByteType;
					encNames[typeof(Nullable<Char>)]    = CharType;
					encNames[typeof(Nullable<Int16>)]   = ShortType;
					encNames[typeof(Nullable<Int32>)]   = IntType;
					encNames[typeof(Nullable<Int64>)]   = LongType;
					encNames[typeof(Nullable<UInt16>)]  = UShortType;
					encNames[typeof(Nullable<UInt32>)]  = UIntType;
					encNames[typeof(Nullable<UInt64>)]  = ULongType;
					encNames[typeof(Nullable<Decimal>)] = DecimalType;
					encNames[typeof(Nullable<Single>)]  = FloatType;
					encNames[typeof(Nullable<Double>)]  = DoubleType;
				}
			}
		}

		// internal type names
		const string BoolType    = ".b";       // Boolean
		const string ByteType    = ".u1";      // Byte
		const string SByteType   = ".s1";      // SByte
		const string CharType    = ".c";       // Char
		const string ShortType   = ".s2";      // Int16
		const string UShortType  = ".u2";      // UInt16
		const string IntType     = ".s4";      // Int32
		const string UIntType    = ".u4";      // UInt32
		const string LongType    = ".s8";      // Int64
		const string ULongType   = ".u8";      // UInt64
		const string DecimalType = ".D";       // Decimal
		const string DoubleType  = ".d";       // Double
		const string FloatType   = ".f";       // Single
		const string ArrayofType = ".arrayof"; // array of primitive
		const string ArrayType   = ".array";   // array of object
		const string StringType  = ".s";       // UTF-8 string
		const string EnumType    = ".e";       // Enum
		const string RefType     = ".r";       // object reference -- appeared earlier
                                               // in the expression. 

        // A type implementing ISerializable
        const string SerialType  = ".serial";

		// A delegate method
		const string FuncType    = ".func";

		const string SRPCCallType     = "srpc-call";
		const string SRPCResponseType = "srpc-response";
		const string SRPCFaultType    = "srpc-fault";

		object ListToObject(List l)
		{
			return ListToObjectCore(l, new List<object>());
		}

        private object ListToObjectCore(List l, List<object> objects)
        {
			int len = l.Count;

			if (len == 0) // null
            {
                objects.Add(null);
				return null;
            }

			if (len < 2 || len > 4)
				throw new SerializationException("incorrect number of elements in object list");

			Expression typexpr = l[0];
			if (!(typexpr is Atom))
				throw new SerializationException("expected an atom type name");
			string typename = ((Atom) typexpr).ToString(null);
			Expression valuexpr = l[1];

            ConvertAtom conv;
            if (decMap.TryGetValue(typename, out conv))
            {
                if (len != 2 || !(valuexpr is Atom))
					throw new SerializationException("invalid " + typename);
				object o = conv((Atom) valuexpr);
                objects.Add(o);
                return o;
			}

			if (typename == ArrayofType)
			{
                if (len != 3)
                    throw new SerializationException("expecting three expressions in .arrayof");
                Atom elem = l[1] as Atom;
                if (elem == null)
                    throw new SerializationException("expecting an atom");
                Atom value = l[2] as Atom;
                if (value == null)
                    throw new SerializationException("expecting an atom");

                byte[] bytes = value.Bytes;
                switch (elem.ToString())
                {
                case BoolType:
                {
                    bool[] result = new bool[bytes.Length];
                    int i = 0;
                    foreach (byte b in bytes) result[i++] = (b != 0);
                    objects.Add(result);
                    return result;
                }

                case ByteType:
                    return bytes;

				case SByteType:
				{
					sbyte[] result = new sbyte[bytes.Length];
					int i = 0;
					foreach (byte b in bytes) result[i++] = unchecked((sbyte) b);
                    objects.Add(result);
					return result;
				}

                case ShortType:
                {
                    if (bytes.Length % 2 != 0)
                        throw new SerializationException();
                    short[] result = new short[bytes.Length / 2];
                    for (int i = 0, j = 0; i < result.Length; i++)
                        result[i] = unchecked((short) (((bytes[j++] & 0xFF) << 8)
													   | (bytes[j++] & 0xFF)));
                    objects.Add(result);
                    return result;
                }

                case UShortType:
                {
                    if (bytes.Length % 2 != 0)
                        throw new SerializationException();
                    ushort[] result = new ushort[bytes.Length / 2];
                    for (int i = 0, j = 0; i < result.Length; i++)
                        result[i] = (ushort) (((bytes[j++] & 0xFF) << 8)
											  | (bytes[j++] & 0xFF));
                    objects.Add(result);
                    return result;
                }

                case IntType:
                {
                    if (bytes.Length % 4 != 0)
                        throw new SerializationException();
                    int[] result = new int[bytes.Length / 4];
                    for (int i = 0, j = 0; i < result.Length; i++)
                        result[i] = unchecked((int) (((bytes[j++] & 0xFF) << 24)
													 | ((bytes[j++] & 0xFF) << 16)
													 | ((bytes[j++] & 0xFF) <<  8)
													 | (bytes[j++] & 0xFF)));
                    objects.Add(result);
                    return result;
                }

                case UIntType:
                {
                    if (bytes.Length % 4 != 0)
                        throw new SerializationException();
                    uint[] result = new uint[bytes.Length / 4];
                    for (int i = 0, j = 0; i < result.Length; i++)
                        result[i] = (uint) (((bytes[j++] & 0xFF) << 24)
											| ((bytes[j++] & 0xFF) << 16)
											| ((bytes[j++] & 0xFF) <<  8)
											| (bytes[j++] & 0xFF));
                    objects.Add(result);
                    return result;
                }

                case LongType:
                {
                    if (bytes.Length % 8 != 0)
                        throw new SerializationException();
                    long[] result = new long[bytes.Length / 8];
                    for (int i = 0, j = 0; i < result.Length; i++)
                        result[i] = unchecked((((long) (bytes[j++] & 0xFF) << 56)
											   | ((long) (bytes[j++] & 0xFF) << 48)
											   | ((long) (bytes[j++] & 0xFF) << 40)
											   | ((long) (bytes[j++] & 0xFF) << 32)
											   | ((long) (bytes[j++] & 0xFF) << 24)
											   | ((long) (bytes[j++] & 0xFF) << 16)
											   | ((long) (bytes[j++] & 0xFF) <<  8)
											   | ((long) (bytes[j++] & 0xFF))));
                    objects.Add(result);
                    return result;
                }

                case ULongType:
                {
                    if (bytes.Length % 8 != 0)
                        throw new SerializationException();
                    ulong[] result = new ulong[bytes.Length / 8];
                    for (int i = 0, j = 0; j < result.Length; i++)
                        result[i] = (((ulong) (bytes[j++] & 0xFF) << 56)
									 | ((ulong) (bytes[j++] & 0xFF) << 48)
									 | ((ulong) (bytes[j++] & 0xFF) << 40)
									 | ((ulong) (bytes[j++] & 0xFF) << 32)
									 | ((ulong) (bytes[j++] & 0xFF) << 24)
									 | ((ulong) (bytes[j++] & 0xFF) << 16)
									 | ((ulong) (bytes[j++] & 0xFF) <<  8)
									 | ((ulong) (bytes[j++] & 0xFF)));
                    objects.Add(result);
                    return result;
                }
                }

                throw new SerializationException("can't decode arrayof " + elem);
			}

			if (typename == ArrayType)
			{
				if (len != 2 && len != 3)
					throw new SerializationException(".array needs two or three elements");
                Atom elemType = null;
                bool explicitType = false;
                if (len == 3)
                {
                    elemType = valuexpr as Atom;
                    if (elemType == null)
                        throw new SerializationException("expecting atom element type");
                    valuexpr = l[2];
                    explicitType = true;
                }
				if (!(valuexpr is List))
					throw new SerializationException("second element of .array must be a list");
				Type commonType = null;
                if (explicitType)
                    commonType = SexpServices.LookupType(elemType.ToString(), cache);
				List elems = (List) valuexpr;
				List<object> items = new List<object>();
                bool sawNull = false;
				foreach (Expression x in elems)
				{
					if (x is Atom)
						throw new SerializationException("found atom in array elements");
					object o = ListToObjectCore((List) x, objects);
					if (o != null && !explicitType)
						commonType = CommonType(commonType, o.GetType());
                    else
                        sawNull = true;
					items.Add(o);
				}
				if (commonType == null || (sawNull && !explicitType))
					commonType = typeof(object);
				Array a = Array.CreateInstance(commonType, items.Count);
				for (int i = 0; i < items.Count; i++)
					a.SetValue(items[i], i);
                objects.Add(a);
				return a;
			}

			if (typename == EnumType)
			{
				if (len != 3)
					throw new SerializationException(".e needs exactly three atoms");
				Atom enumtype = valuexpr as Atom;
				Atom value = l[2] as Atom;
				if (enumtype == null || value == null)
					throw new SerializationException(".e needs exactly three atoms");
				Type etype = SexpServices.LookupType(enumtype.ToString(), null, cache, binder);
				object o = Enum.ToObject(etype, value.ToInteger());
				if (o == null)
					throw new SerializationException("unknown enum value for " +
													 etype + ": " + value.ToInteger());
                objects.Add(o);
				return o;
			}

            // FIXME this should just use ObjectManager
            if (typename == RefType)
            {
                if (len != 2)
                    throw new SerializationException(".r needs exactly two atoms");
                Atom refnum = valuexpr as Atom;
                if (refnum == null)
                    throw new SerializationException(".r value must be an atom");
                int r = Convert.ToInt32(refnum);
                if (r < 0 || r >= objects.Count)
                    throw new SerializationException("invalid reference: " + r);
                return objects[r];
            }

            if (typename == FuncType)
            {
                if (len != 2)
                    throw new SerializationException(".func needs exactly two expressions");
                List func = valuexpr as List;
                if (func == null)
                    throw new SerializationException(".func value should be a list");
                if (func.Count != 4)
                    throw new SerializationException(".func value needs four expressions");

                List typelist = func[0] as List;
                if (typelist == null)
                    throw new SerializationException(".func type list must be a list");
                Atom funcIL = func[1] as Atom;
                if (funcIL == null)
                    throw new SerializationException(".func IL value must be an atom");
                Atom maxStack = func[2] as Atom;
                if (maxStack == null)
                    throw new SerializationException(".func max stack value must be an atom");
                List locals = func[3] as List;
                if (locals == null)
                    throw new SerializationException(".func locals must be a list");

                if (typelist.Count < 1 || typelist.Count > 5)
                    throw new SerializationException(".func type list must have 1 to 5 elements");

                Atom rtatom = typelist[0] as Atom;
                if (rtatom == null)
                    throw new SerializationException(".func type list elements must be atoms");
                Type returnType = SexpServices.LookupType(rtatom.ToString(), cache);
                if (returnType == null)
                    throw new SerializationException("type not found: " + rtatom);

                Type[] paramTypes = new Type[typelist.Count];
                paramTypes[0] = typeof(object);
                for (int i = 1; i < paramTypes.Length; i++)
                {
                    Atom tatom = typelist[i] as Atom;
                    if (tatom == null)
                        throw new SerializationException(".func type list elements must be atoms");
                    paramTypes[i] = SexpServices.LookupType(tatom.ToString(), cache);
                    if (paramTypes[i] == null)
                        throw new SerializationException("type not found: " + tatom);
                }
                Type[] funcTypes = new Type[paramTypes.Length+1];
                Type[] finalTypes = new Type[paramTypes.Length];
                Type[] paramsOnly = new Type[paramTypes.Length-1];
                funcTypes[0] = typeof(object);
                for (int i = 1; i < paramTypes.Length; i++)
                {
                    funcTypes[i] = paramTypes[i];
                    finalTypes[i-1] = paramTypes[i];
                    paramsOnly[i-1] = paramTypes[i];
                }
                funcTypes[funcTypes.Length - 1] = returnType;
                finalTypes[finalTypes.Length - 1] = returnType;
                Type targetType = null;
                Type finalType = null;
                Type bagType = null;
                switch (paramTypes.Length)
                {
                case 1:
                    targetType = typeof(Func<,>).MakeGenericType(funcTypes);
                    finalType = typeof(Func<>).MakeGenericType(finalTypes);
                    bagType = typeof(__func_bag<>).MakeGenericType(finalTypes);
                    break;

                case 2:
                    targetType = typeof(Func<,,>).MakeGenericType(funcTypes);
                    finalType = typeof(Func<,>).MakeGenericType(finalTypes);
                    bagType = typeof(__func_bag<,>).MakeGenericType(finalTypes);
                    break;

                case 3:
                    targetType = typeof(Func<,,,>).MakeGenericType(funcTypes);
                    finalType = typeof(Func<,,>).MakeGenericType(finalTypes);
                    bagType = typeof(__func_bag<,,>).MakeGenericType(finalTypes);
                    break;

                case 4:
                    targetType = typeof(Func<,,,,>).MakeGenericType(funcTypes);
                    finalType = typeof(Func<,,,>).MakeGenericType(finalTypes);
                    bagType = typeof(__func_bag<,,,>).MakeGenericType(finalTypes);
                    break;

                case 5:
                    targetType = typeof(__func<,,,,,>).MakeGenericType(funcTypes);
                    finalType = typeof(Func<,,,,>).MakeGenericType(finalTypes);
                    bagType = typeof(__func_bag<,,,,>).MakeGenericType(finalTypes);
                    break;
                }

                SignatureHelper helper = SignatureHelper.GetLocalVarSigHelper();
                foreach (Expression e in locals)
                {
                    List local = e as List;
                    if (local == null)
                        throw new SerializationException("local var must be a list");
                    if (local.Count != 2)
                        throw new SerializationException("local var must be a pair");
                    Atom localtype = local[0] as Atom;
                    Atom pinned = local[1] as Atom;
                    if (localtype == null || pinned == null)
                        throw new SerializationException("local var must be a pair of atoms");
                    helper.AddArgument(SexpServices.LookupType(localtype.ToString(), cache),
                                       Convert.ToBoolean(pinned));
                }

                DynamicMethod dm = new DynamicMethod("<>__sexp_generated_" + func.GetHashString(),
                                                     returnType, paramTypes, targetType);
                DynamicILInfo dil = dm.GetDynamicILInfo();
                dil.SetCode(funcIL.Bytes, Convert.ToInt32(maxStack));
                dil.SetLocalSignature(helper.GetSignature());

                ConstructorInfo ctor = bagType.GetConstructor(new Type[] { typeof(object),
                                                                           typeof(DynamicMethod) });
                MethodInfo bagInvoke = bagType.GetMethod("do_invoke", paramsOnly);
                object bag = ctor.Invoke(new object[] { null, dm });
                // return dm.CreateDelegate(targetType/*, new __func_bag()*/);
                return Delegate.CreateDelegate(finalType, bag, bagInvoke);
            }

			Type type = null;

            // ISerializable, MarshalByRefObject
            if (typename == SerialType)
            {
                if (len != 4)
                    throw new SerializationException(".serial needs exactly four expressions");
                Atom realtype = l[1] as Atom;
                Atom assyname = l[2] as Atom;
                List serialInfo = l[3] as List;

                if (realtype == null || assyname == null || serialInfo == null)
                    throw new SerializationException(".serial expects two atoms and a list");
                type = SexpServices.LookupType(realtype.ToString(), assyname.ToString(), cache,
                                               binder);
                object objRet = FormatterServices.GetUninitializedObject(type);
                SerializationInfo serial = new SerializationInfo(type, new FormatterConverter());

                if (!(objRet is ISerializable) && selector != null)
                {
                    ISurrogateSelector iss;
                    ISerializationSurrogate surrogate = selector.GetSurrogate(type, context,
                                                                              out iss);
                }

                ObjectManager mgr = new ObjectManager(null, context);
                foreach (Expression e in serialInfo)
                {
                    List entry = e as List;
                    if (entry == null)
                        throw new SerializationException("serialization entry must be a list");
                    if (entry.Count != 2)
                        throw new SerializationException("serialization entry must have exactly two expressions");
                    Atom name = entry[0] as Atom;
                    List value = entry[1] as List;
                    if (name == null || value == null)
                        throw new SerializationException("");
                    serial.AddValue(name.ToString(), ListToObjectCore(value, objects));
                }

                mgr.RegisterObject(objRet, 31337, serial);
                __proxy_bag bag = new __proxy_bag();
                mgr.RegisterObject(bag, 0xBA5);
                mgr.RecordFixup(0xBA5, __proxy_value_info, 31337);
                mgr.DoFixups();
                objects.Add(bag.value);
                return bag.value;
            }

            // Internal SRPC types.
			if (typename == SRPCCallType)
				type = typeof(SexpCall);
			if (typename == SRPCResponseType)
				type = typeof(SexpResponse);
			if (typename == SRPCFaultType)
				type = typeof(SexpFault);

			Atom assembly = null;
			if (len == 3)
			{
				assembly = valuexpr as Atom;
				valuexpr = l[2];
			}

			if (type == null)
                type = SexpServices.LookupType(typename,
											   assembly != null ? assembly.ToString() : null,
											   cache, binder);
			if (type == null)
				throw new SerializationException("unknown type: " + typename);

			List valuelist = valuexpr as List;
			if (valuelist == null)
				throw new SerializationException("object value must be a list");

            if (typeof(System.Collections.IList).IsAssignableFrom(type))
            {
                ConstructorInfo ctor = type.GetConstructor(new Type[0]);
                if (ctor != null)
                {
                    System.Collections.IList list
                        = (System.Collections.IList) ctor.Invoke(new object[0]);
                    objects.Add(list);
                    foreach (Expression expr in valuelist)
                    {
                        if (!(expr is List))
                            throw new SerializationException("expecting a list for IList object");
                        list.Add(ListToObjectCore((List) expr, objects));
                    }
                    return list;
                }
            }

            if (typeof(System.Collections.IDictionary).IsAssignableFrom(type))
            {
                ConstructorInfo ctor = type.GetConstructor(new Type[0]);
                if (ctor != null)
                {
                    System.Collections.IDictionary dict = 
                        (System.Collections.IDictionary) ctor.Invoke(new object[0]);
                    objects.Add(dict);
                    foreach (Expression expr in valuelist)
                    {
                        if (!(expr is List))
                            throw new SerializationException("expecting a list for IDictionary object");
                        List kv = (List) expr;
                        if (kv.Count != 2 || !(kv[0] is List) || !(kv[1] is List))
                            throw new SerializationException("expecting key/value pair (list of two lists)");
                        object key = ListToObjectCore((List) kv[0], objects);
                        object val = ListToObjectCore((List) kv[1], objects);
                        dict.Add(key, val);
                    }
                    return dict;
                }
            }
            // else if (typeof(System.Collections.IList<>).IsInstanceOfType(obj))
            // {
            //     Type[] param = new Type[] { typeof(Int32),
            //                                 obj.GetType().GetGenericArguments()[0] };
            //     MethodInfo insert = obj.GetType().GetMethod("Insert", param);
            //     int i = 0;
            //     foreach (Expression expr in ValueList)
            //     {
            //         if (!(expr is List))
            //             throw new SerializationException("expecting a list for IList object");
            //         object o = ListToObjectCore((List) expr, objects);
            //         insert.Invoke(obj, new object[] { i++, o });
            //     }
            //     return obj;
            // }
            // else if (typeof(System.Collections.IDictionary<,>).IsInstanceOfType(obj))
            // {
            //     Type[] param = obj.GetType().GetGenericArguments();
            //     MethodInfo add = obj.GetType().GetMethod("Add", param);
            //     foreach (Expression expr in ValueList)
            //     {
            //         if (!(expr is List))
            //             throw new SerializationException("expecting a list for IDictionary object");
            //         List kv = (List) expr;
            //         if (kv.Length != 2 || !(kv[0] is List) || !(kv[1] is List))
            //             throw new SerializationException("expecting key/value pair (list of two lists)");
            //         object key = ListToObjectCore((List) kv[0], objects);
            //         object val = ListToObjectCore((List) kv[1], objects);
            //         add.Invoke(obj, new object[] { key, val });
            //     }
            //     return obj;
            // }

			object obj = FormatterServices.GetUninitializedObject(type);
            objects.Add(obj);
			MemberInfo[] fields = FormatterServices.GetSerializableMembers(type, context);
			object[] values = new object[fields.Length];
			object[] attr = type.GetCustomAttributes(typeof(SexpFixed), true);
			if (attr.Length > 0)
			{
				if (fields.Length != valuelist.Count)
					throw new SerializationException("invalid fixed struct "
													 + "(the serialized object is corrupt, or the "
													 + "structure layout has changed)");
				int i = 0;
				foreach (Expression expr in valuelist)
				{
					if (expr is Atom)
					{
						Type t = ((FieldInfo) fields[i]).FieldType;
						string iname;
						if (!encNames.TryGetValue(t, out iname))
							throw new SerializationException("atom found for non-primitive type");
						ConvertAtom conv2;
						if (!decMap.TryGetValue(iname, out conv2))
							throw new SerializationException("no primitive converter found");
						values[i++] = conv2((Atom) expr);
					}
					else
						values[i++] = ListToObjectCore((List) expr, objects);
				}
			}
			else
			{
				foreach (Expression expr in valuelist)
				{
					List value = expr as List;
					if (value == null)
						throw new SerializationException("expecting object value list");
					if (value.Count != 2)
						throw new SerializationException("expecting two expressions in object value");
					Atom fieldName = value[0] as Atom;
					if (fieldName == null)
						throw new SerializationException("expecting field name atom; current list: "
                                                         + l + "; expr: " + value);
					List fieldValue = value[1] as List;
					if (fieldValue == null)
						throw new SerializationException("expecting field value list");
					string name = fieldName.ToString();
					bool found = false;
					for (int i = 0; i < fields.Length; i++)
					{
						if (fields[i].Name == name)
						{
							found = true;
							values[i] = ListToObjectCore(fieldValue, objects);
							break;
						}

						attr = fields[i].GetCustomAttributes(typeof(SexpFieldName), true);
						if (attr.Length > 0)
							if (((SexpFieldName) attr[0]).FieldName == name)
							{
								found = true;
								values[i] = ListToObjectCore(fieldValue, objects);
								break;
							}
					}
					if (!found && !boolParams[BooleanParameter.IgnoreExtraFields])
						throw new SerializationException("no field named " + name + " in type "
														 + type);
				}
			}
			FormatterServices.PopulateObjectMembers(obj, fields, values);

            // if (obj is ObjRef)
            //     return RemotingServices.Unmarshal((ObjRef) obj);

			return obj;
		}

		static Type CommonType(Type t1, Type t2)
		{
			if (t1 == null)
			{
				if (t2 == null)
					throw new ArgumentNullException();
				return t2;
			}
			if (t2 == null)
			{
				if (t1 == null)
					throw new ArgumentNullException();
				return t1;
			}
			if (t1 == t2)
				return t1;
			if (t2.IsSubclassOf(t1))
				return t1;
			if (t1.IsSubclassOf(t2))
				return t2;
			return CommonType(t1.BaseType, t2.BaseType);
		}

		List ObjectToList(object o)
		{
            return ObjectToListCore(o, new List<object>());
        }

        private List ObjectToListCore(object o, List<object> objects)
        {
			if (o == null)
			{
				return new List();
			}

            for (int i = 0; i < objects.Count; i++)
            {
                if (Object.ReferenceEquals(o, objects[i]))
                {
                    List l = new List();
                    l.Add(new Atom(RefType));
                    l.Add(new Atom(i));
                    return l;
                }
            }

            objects.Add(o);

            ConvertPrim conv;
            Type type = o.GetType();
            if (encMap.TryGetValue(type, out conv))
            {
                string name;
                if (encNames.TryGetValue(type, out name))
                {
                    List list = new List();
                    list.Add(new Atom(name));
                    list.Add(conv(o));
                    return list;
                }
            }

			if (o is bool[])
			{
				bool[] a = (bool[]) o;
				byte[] b = new byte[a.Length];
				for (int i = 0; i < a.Length; i++)
					b[i] = (byte) (a[i] ? 1 : 0);
				List l = new List();
				l.Add(new Atom(ArrayofType));
				l.Add(new Atom(BoolType));
				l.Add(new Atom(b));
				return l;
			}
			if (o is byte[])
			{
				List l = new List();
				l.Add(new Atom(ArrayofType));
				l.Add(new Atom(ByteType));
				l.Add(new Atom((byte[]) o));
				return l;
			}
#if no_gravy
			if (o is sbyte[])
			{
				List l = new List();
				l.Add(new Atom(ArrayofType));
				l.Add(new Atom(SByteType));
				l.Add(new Atom(((sbyte[]) o).ToBytes()));
				return l;
			}
			if (o is ushort[])
			{
				List l = new List();
				l.Add(new Atom(ArrayofType));
				l.Add(new Atom(UShortType));
				l.Add(new Atom(((ushort[]) o).ToBytes()));
				return l;
			}
			if (o is short[])
			{
				List l = new List();
				l.Add(new Atom(ArrayofType));
				l.Add(new Atom(ShortType));
				l.Add(new Atom(((short[]) o).ToBytes()));
				return l;
			}
			if (o is uint[])
			{
				List l = new List();
				l.Add(new Atom(ArrayofType));
				l.Add(new Atom(UIntType));
				l.Add(new Atom(((uint[]) o).ToBytes()));
				return l;
			}
			if (o is int[])
			{
				List l = new List();
				l.Add(new Atom(ArrayofType));
				l.Add(new Atom(IntType));
				l.Add(new Atom(((int[]) o).ToBytes()));
				return l;
			}
			if (o is ulong[])
			{
				List l = new List();
				l.Add(new Atom(ArrayofType));
				l.Add(new Atom(ULongType));
				l.Add(new Atom(((ulong[]) o).ToBytes()));
				return l;
			}
			if (o is long[])
			{
				List l = new List();
				l.Add(new Atom(ArrayofType));
				l.Add(new Atom(LongType));
				l.Add(new Atom(((long[]) o).ToBytes()));
				return l;
			}
#endif

			if (o is Array)
			{
                Array a = o as Array;
                if (a.IsConvertibleToBytes())
                {
                    List l = new List();
                    l.Add(new Atom(ArrayofType));
                    l.Add(new Atom(encNames[a.GetType().GetElementType()]));
                    l.Add(new Atom(a.ToBytes()));
                    return l;
                }
                else
                {
                    List l = new List();
                    l.Add(new Atom(ArrayType));
                    l.Add(new Atom(SexpServices.TypeNameForType(type.GetElementType())));
                    List ll = new List();
                    foreach (object oo in ((object[]) o))
                        ll.Add(ObjectToListCore(oo, objects));
                    l.Add(ll);
                    return l;
                }
			}

			if (o is Enum)
			{
				List list = new List();
				list.Add(new Atom(EnumType));
                list.Add(new Atom(SexpServices.TypeNameForType(type)));
				list.Add(new Atom(Convert.ToUInt32(o), true));
				return list;
			}

			if (o is Delegate && type.IsGenericType
				&& (typeof(Func<>) == type.GetGenericTypeDefinition()
					|| typeof(Func<,>) == type.GetGenericTypeDefinition()
					|| typeof(Func<,,>) == type.GetGenericTypeDefinition()
					|| typeof(Func<,,,>) == type.GetGenericTypeDefinition()
					|| typeof(Func<,,,,>) == type.GetGenericTypeDefinition()))
			{
				List list = new List();
				MethodInfo method = ((Delegate) o).Method;
				Console.WriteLine("method is " + method);
				MethodBody body = method.GetMethodBody();
				Console.WriteLine("method body is " + body);
				list.Add(new Atom(FuncType));
				List func = new List();
				List typelist = new List();
				Type[] types = type.GetGenericArguments();
				foreach (Type t in types)
					typelist.Add(new Atom(SexpServices.TypeNameForType(t)));
				func.Add(typelist);
				func.Add(new Atom(body.GetILAsByteArray()));
                func.Add(new Atom(body.MaxStackSize));

                List locals = new List();
                foreach (LocalVariableInfo info in body.LocalVariables)
                {
                    List local = new List();
                    local.Add(new Atom(SexpServices.TypeNameForType(info.LocalType)));
                    local.Add(new Atom(info.IsPinned));
                    locals.Add(local);
                }
                func.Add(locals);

				list.Add(func);
				return list;
			}

            ISurrogateSelector next_selector = null;
            ISerializationSurrogate surrogate = null;
            if (selector != null)
                surrogate = selector.GetSurrogate(type, context, out next_selector);

            if (o is ISerializable || surrogate != null)
            {
                SerializationInfo serial = new SerializationInfo(type, new FormatterConverter());
                if (surrogate != null)
                    surrogate.GetObjectData(o, serial, context);
                else
                    ((ISerializable) o).GetObjectData(serial, context);
                List list = new List();
                list.Add(new Atom(SerialType));
                list.Add(new Atom(serial.FullTypeName));
                list.Add(new Atom(serial.AssemblyName));
                List serialMembers = new List();
                foreach (SerializationEntry e in serial)
                {
                    List member = new List();
                    member.Add(new Atom(e.Name));
                    member.Add(ObjectToListCore(e.Value, objects));
                    serialMembers.Add(member);
                }
                list.Add(serialMembers);
                return list;
            }

            if (o is System.Collections.IList)
            {
                List list = new List();
                list.Add(new Atom(SexpServices.TypeNameForType(type)));
                if (SexpServices.TypeWithAssembly(type))
                    list.Add(new Atom(type.Assembly.GetName().Name));

                List values = new List();
                foreach (object item in (System.Collections.IList) o)
                    values.Add(ObjectToListCore(item, objects));
                list.Add(values);
                return list;
            }

            if (o is System.Collections.IDictionary)
            {
                List list = new List();
                list.Add(new Atom(SexpServices.TypeNameForType(type)));
                if (SexpServices.TypeWithAssembly(type))
                    list.Add(new Atom(type.Assembly.GetName().Name));

                List values = new List();
                foreach (System.Collections.DictionaryEntry e in (System.Collections.IDictionary) o)
                {
                    object key = e.Key;
                    object value = e.Value;
                    List kv = new List();
                    kv.Add(ObjectToListCore(key, objects));
                    kv.Add(ObjectToListCore(value, objects));
                    values.Add(kv);
                }
                list.Add(values);
                return list;
            }

			{
				List list = new List();
				MemberInfo[] fields = FormatterServices.GetSerializableMembers(type, context);
                object[] values = FormatterServices.GetObjectData(o, fields);

				// Handle "fixed" structures.
				object[] attr = type.GetCustomAttributes(typeof(SexpFixed), true);
				if (attr.Length > 0)
				{
                    list.Add(new Atom(SexpServices.TypeNameForType(type)));
                    if (SexpServices.TypeWithAssembly(type))
                        list.Add(new Atom(type.Assembly.GetName().Name));

					List fieldList = new List();
                    for (int i = 0; i < values.Length; i++)
					{
						ConvertPrim conv2 = null;
						if (encMap.TryGetValue(((FieldInfo) fields[i]).FieldType, out conv2))
							fieldList.Add(conv2(values[i]));
						else
							fieldList.Add(ObjectToListCore(values[i], objects));
					}
					list.Add(fieldList);
					return list;
				}

				// Handle any other object.
                list.Add(new Atom(SexpServices.TypeNameForType(type)));
                if (SexpServices.TypeWithAssembly(type))
                    list.Add(new Atom(type.Assembly.GetName().Name));

				List ll = new List();
                for (int i = 0; i < values.Length; i++)
				{
					List field = new List();
					if ((attr = fields[i].GetCustomAttributes(typeof(SexpFieldName), false)).Length > 0)
						field.Add(new Atom(((SexpFieldName) attr[0]).FieldName));
					else
						field.Add(new Atom(fields[i].Name));
					field.Add(ObjectToListCore(values[i], objects));
					ll.Add(field);
				}
				list.Add(ll);
				return list;
			}
		}
	}
}